package two.chapter_1.c1_4;

public class EggDropper {

    private int F=6;//鸡蛋从F层或者更高的地方扔下会摔碎

    /**
     * 二分法查找  需要扔logN个鸡蛋找到F层。
     * @param floors
     * @return
     */
    public int dropEgg(int floors){
        int lo=1;
        int hi=floors;
        while (lo<=hi){
            int mid=lo+(hi-lo)/2;
            if (broke(mid)){
                hi=mid-1;
            }else {
                lo=mid+1;
            }

        }
        return lo;
    }

    private boolean broke(int floor) {
       return floor>=F;
    }

    /**
     * 按照第 1, 2, 4, 8,..., 2^k 层顺序查找，一直到 2^k > F，
     * 随后在 [2^(k - 1), 2^k] 范围中二分查找。
     * ~2logF
     * @param floors
     * @return
     */
    public int dropEggFast(int floors){
        int k=0;
        int lo=1;
        int hi=1;
        while (!broke(hi)){
            lo=hi;
            hi*=2;
        }

       if (hi>floors){
            hi=floors;
       }

       while (lo<=hi){
            int mid=lo+(hi-lo)/2;
            if (broke(mid)){
                hi=mid-1;
            }else {
                lo=mid+1;
            }
       }
       return lo;
    }
}
